#include <iostream>
#include <vector>
using namespace std;
int Func1(int vol, vector<int>& cost, vector<int>& value) {
  int len = cost.size();
  // dp[i][j]表示从下标0-i的物品中选，装入容量为j的背包能获得的最大价值
  vector<vector<int> > dp(len, vector<int>(vol + 1, 0));
  for (int i = cost[0]; i <= vol; i++) {
    dp[0][i] = value[0];
  }
  for (int i = 1; i < len; i++) {
    for (int j = 0; j <= vol; j++) {
      if (j < cost[i])
        dp[i][j] = dp[i - 1][j];
      else
        dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cost[i]] + value[i]);
    }
  }
  return dp[len - 1][vol];
}
int Func2(int vol, vector<int>& cost, vector<int>& value) {
  int len = cost.size();
  // dp[j]表示容量为j的背包能装入物品的最大价值
  // 让dp数组在递归公式的过程中取的最大的价值，而不是被初始值覆盖（正0，负负无穷）
  vector<int> dp(vol + 1, 0);
  // 不可交换两个for循环的顺序，否则每个dp[j]就只会放入一个物品，即：背包里只放入了一个物品。
  for (int i = 0; i < len; i++) {
    for (int j = vol; j >= cost[i]; j--) {
      // 倒叙遍历是为了保证物品i只被放入一次！
      dp[j] = max(dp[j], dp[j - cost[i]] + value[i]);
    }
  }
  return dp[vol];
}
int main() {
  vector<int> cost{1, 3, 4};
  vector<int> value{15, 20, 30};
  int vol = 4;
  cout << Func1(vol, cost, value) << endl;
  cout << Func2(vol, cost, value) << endl;
  return 0;
}